1. Field of the Invention
The field of the invention relates to queuing systems in a computer system. Specifically, the present invention relates to multiple-reader multiple-writer queues.
2. Description of Related Art
The circular queue invention herein provides a mechanism and method for producers of fixed-size data items to deliver those items to consumers even under circumstances in which multiple producers and multiple consumers share the same queue. Any producer or consumer can be permitted to preempt any producer or consumer at any time without interfering with the correctness of the queue.
Current queue implementations suffer from one or more disadvantages that stem from the need to maintain consistency of the queue data structures in spite of that fact that multiple agents manipulate them:
1. Queue implementations based on linked lists invariably involve a "critical region" within which several links must be manipulated indivisibly with respect to one another. PA1 2. Queue implementations based on simple circular buffers avoid these critical regions by limiting themselves to a single variable being manipulated exclusively by either a reader or a writer, not both, but as a result they become limited to a single producer and a single consumer. PA1 3. Avoiding the limitations of (1) and (2) usually involves preventing other agents such as interrupt handlers or preemptively scheduled processes from preempting an agent while it is in a critical region. On most prior art processors, instructions used to enforce critical regions require an additional privilege level not usually available to user code. PA1 4. Avoiding the privilege limitation of (3) involves a performance burden in the form of either a procedure call to an operating system function that enforces critical regions or fault-handling code that "traps" some privileged instructions and simulates them. PA1 5. In some cases it is possible to use a "spin-lock" implementation of critical regions without special privilege or performance overhead by appropriate use of a (non-privileged) "indivisible test-and-set" instruction. The use of a "spin-lock" is well known in the art. However, these cases are limited to ones in which the competing agents are independently scheduled, e.g., running on different processors or in a preemptively scheduled multitasking environment.
Thus, a queue supporting multiple producers and multiple consumers is needed.